package demo.hw;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。
 * 每个柱子彼此相邻，且宽度为 1 。
 * 注意这里宽度为1
 *
 * @author taqo
 * @date 2021/5/29
 */
public class _机试1求最大面积 {
    public static void main(String[] args) {
        // 提交后老是报数组越界？？
        // int[] a = {1,1}; // 2
        // int[] a = {2, 4}; // 4
        // int[] a = {2,15,5,6,2,3}; // 15
        // int[] a = {1 , 8 , 6 , 2 , 5 , 4 , 8 , 3 , 7}; // 49
        int[] a = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; // 25
        maxArea0(a);
        maxArea3(a);
        maxArea2(a);
        maxArea(a);
    }

    // 这个解决不了[2,4]
    private static void maxArea(int[] heights) {
        int max = 0;
        // for (int i = 0; i < a.length; i++) {
        // 机试提交后老是报数组越界？？ 这里减1
        for (int i = 0; i < heights.length - 1; i++) {
            for (int j = i + 1; j < heights.length; j++) {
                int h = Math.min(heights[i], heights[j]);
                int w = j - i + 1;
                max = Math.max(max, h * w);
            }
        }
        System.out.println(max);
    }

    // 这种会超时,仍然不准确
    private static void maxArea2(int[] heights) {
        if (heights.length < 2) {
            System.out.println(heights[0]);
            return;
        }
        int max = 0;
        // for (int i = 0; i < a.length; i++) {
        // 机试提交后老是报数组越界？？ 这里减1
        for (int i = 0; i < heights.length - 1; i++) { // 问题1
            int h = Integer.MAX_VALUE;
            for (int j = i; j < heights.length; j++) {
                h = Math.min(h, heights[j]); // 问题2 h
                int w = j - i + 1;
                max = Math.max(max, h * w);
            }
        }
        System.out.println(max);
    }

    private static void maxArea3(int[] heights) {
        if (heights.length < 2) {
            System.out.println(heights[0]);
            return;
        }
        int left = 0, right = heights.length - 1, max = 0,area = 0;
        while (left < right) {
            int h = Math.min(heights[left], heights[right]);
            area = h * (right - left);
            max = Math.max(max, area);

            // 小的往中间靠
            if (heights[left] < heights[right]) {
                left++;
            } else {
                right--;
            }
        }
        System.out.println(max);
    }

    // 解决不了1，1
    public static void maxArea0(int[] height) {
        int maxarea = 0, left = 0, right = height.length - 1;
        int area = 0;
        while (left < right) {
            //计算面积，面积等于宽*高，宽就是left和right之间的距离，高就是
            //left和right所对应的最低高度
            area = Math.min(height[left], height[right]) * (right - left);
            //保存计算过的最大的面积
            maxarea = Math.max(maxarea, area);
            //柱子矮的往中间靠
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        System.out.println(maxarea);
    }
}
